﻿#include "BinaryTree.h"
#include <iostream>

typedef struct {
	bool isEmpty;
	bool isSearchingTree;
	BinaryTreeNode* root;
	size_t nodeCount;
	int maxValue;
	int minValue;
}FindBiggestBinartSearchingTreeData;

#define DEFALUT_MAX 0x1fffffff
#define DEFALUT_MIN -1

#define MAX(a, b) (a > b ? a : b)
#define MIN(a, b) (a < b ? a : b)

static FindBiggestBinartSearchingTreeData returnTreeData(BinaryTreeNode* head)
{
	FindBiggestBinartSearchingTreeData data = { 
		false,
		false, 
		nullptr, 
		0, 
		DEFALUT_MAX, 
		DEFALUT_MIN,
	};

	if (!head)
	{
		data.isEmpty = true;
		data.isSearchingTree = true;
		return data;
	}

	auto leftData = returnTreeData(head->left);
	auto rightData = returnTreeData(head->right);

	if (leftData.isEmpty && rightData.isEmpty)
	{
		data.isSearchingTree = true;
		data.maxValue = head->getValue();
		data.minValue = head->getValue();
		data.nodeCount = 1;
		data.root = head;
		return data;
	}

	if (leftData.isEmpty && !rightData.isEmpty)
	{
		if (rightData.isSearchingTree)
		{
			if (head->getValue() < rightData.minValue)
			{
				data.isSearchingTree = true;
				data.maxValue = rightData.maxValue;
				data.minValue = head->getValue();
				data.nodeCount = 1 + rightData.nodeCount;
				data.root = head;
				return data;
			}
			else
			{
				data = rightData;
				data.isSearchingTree = false;
				return data;
			}
		}
		else
		{
			return rightData;
		}
	}

	if (!leftData.isEmpty && rightData.isEmpty)
	{
		if (leftData.isSearchingTree)
		{
			if (head->getValue() > leftData.maxValue)
			{
				data.isSearchingTree = true;
				data.maxValue = head->getValue();
				data.minValue = leftData.minValue;
				data.nodeCount = 1 + leftData.nodeCount;
				data.root = head;
				return data;
			}
			else
			{
				data = leftData;
				data.isSearchingTree = false;
				return data;
			}
		}
		else
		{
			return leftData;
		}
	}

	if (leftData.isSearchingTree && rightData.isSearchingTree)
	{
		if (leftData.maxValue < head->getValue() && head->getValue() < rightData.minValue)
		{
			data.isSearchingTree = true;
			data.minValue = leftData.minValue;
			data.maxValue = rightData.maxValue;
			data.nodeCount = 1 + leftData.nodeCount + rightData.nodeCount;
			data.root = head;
			return data;
		}
		else
		{
			data = rightData.nodeCount > leftData.nodeCount ? rightData : leftData;
			data.isSearchingTree = false;
			return data;
		}
	}

	if (leftData.isSearchingTree && !rightData.isSearchingTree)
	{
		data = leftData;
		data.isSearchingTree = false;
		return data;
	}

	if (!leftData.isSearchingTree && rightData.isSearchingTree)
	{
		data = rightData;
		data.isSearchingTree = false;
		return data;
	}

	data = leftData.nodeCount > rightData.nodeCount ? leftData : rightData;
	data.isSearchingTree = false;
	return data;
}

// 找到一颗二叉树中，最大的搜索二叉子树，返回最大搜索二叉子树的节点个数和根节点
//
// 思路：
// 对于某一个节点head，如果含有BST，则有3种可能性
// 1. 以head为根节点的子树不是BST，但是它的左子树是BST
// 2. 以head为根节点的子树不是BST，但是它的右子树是BST
// 3. 以head为根节点的子树是BST
int main_FindBiggestBinarySearchingTree()
{
	auto head = new BinaryTreeNode(20);
	head->left = new BinaryTreeNode(15);
	head->left->left = new BinaryTreeNode(10);
	head->left->right = new BinaryTreeNode(18);
	head->right = new BinaryTreeNode(26);
	head->right->left = new BinaryTreeNode(22);
	head->right->right = new BinaryTreeNode(29);
	head->right->left->left = new BinaryTreeNode(21);

	auto data = returnTreeData(head);
	printf("root=%d,0x%08x, count=%d\n", data.root ? data.root->getValue() : -1, data.root, data.nodeCount);

	deleteBinaryTree(head);
	return 0;
}